package com.example.system.class13;

/**
 * @Date 2022/8/2
 * @Author Jonathan
 * @Description 最大二叉搜索子树的节点数
 */
public class Code06_MaxSubBSTSize {
    private static int index = 0;

    public static void main(String[] args) {
        Integer[] arr = new Integer[]{1, 3, 2, null, null, 5, 4, null, null, null, null};
        Info info = getMaxBSTSize(createBT(arr));
        System.out.println(info.maxSubBSTSize);
        System.out.println(info.root);
    }


    public static Info getMaxBSTSize(Node root) {
        return process(root);
    }


    public static Info process(Node x) {
        if (x == null) {
            return null;
        }

        Info left = process(x.left);
        Info right = process(x.right);
        Node root;
        int maxSubBSTSize;
        if (left != null && right != null) {
            int min = Math.min(left.min, right.min);
            int max = Math.max(left.max, right.max);
            boolean isBst = left.isBst && right.isBst && left.max <= x.value && x.value <= right.min;
            if (isBst) {
                maxSubBSTSize = left.maxSubBSTSize + right.maxSubBSTSize + 1;
                root = x;
            } else if (left.maxSubBSTSize > right.maxSubBSTSize) {
                maxSubBSTSize = left.maxSubBSTSize;
                root = left.root;
            } else {
                maxSubBSTSize = right.maxSubBSTSize;
                root = right.root;
            }
            return new Info(max, min, maxSubBSTSize, isBst, root);
        }

        // left!=null right==null
        if (left != null) {
            int min = Math.min(left.min, x.value);
            int max = Math.max(left.max, x.value);
            boolean isBst = left.isBst && left.max <= x.value;
            if (isBst) {
                maxSubBSTSize = (left.maxSubBSTSize + 1);
                root = x;
            } else {
                maxSubBSTSize = left.maxSubBSTSize;
                root = left.root;
            }
            return new Info(max, min, maxSubBSTSize, isBst, root);
        }
        //  left==null right!=null
        if (right != null) {
            int min = Math.min(right.min, x.value);
            int max = Math.max(right.max, x.value);
            boolean isBst = right.isBst && right.min >= x.value;
            if (isBst) {
                maxSubBSTSize = (right.maxSubBSTSize + 1);
                root = x;
            } else {
                maxSubBSTSize = right.maxSubBSTSize;
                root = right.root;
            }
            return new Info(max, min, maxSubBSTSize, isBst, root);

        }

        // left==null && right==null
        return new Info(x.value, x.value, 1, true, x);

    }


    public static Node createBT(Integer[] arr) {
        if (arr == null || arr.length <= 0) {
            return null;
        }
        return create(arr);
    }

    // 借助全局变量实现
    public static Node create(Integer[] arr) {
        Integer value = arr[index++];
        if (value == null) {
            return null;
        }
        final Node node = new Node(value);
        node.left = create(arr);
        node.right = create(arr);
        return node;
    }


    public static class Info {
        Integer max;
        Integer min;
        int maxSubBSTSize;
        boolean isBst;
        Node root;

        public Info(Integer max, Integer min, int maxSubBSTSize, boolean isBst, Node root) {
            this.max = max;
            this.min = min;
            this.maxSubBSTSize = maxSubBSTSize;
            this.isBst = isBst;
            this.root = root;
        }
    }

    public static class Node {
        Node left;
        Node right;
        int value;

        public Node(int value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return "Node[" +
                    "" + value +
                    ']';
        }
    }

}
